package NP;
import java.util.Iterator;


	//La classe NP
public abstract class NP extends ExpTime{
			//pour un NP on doit pouvoir d�finir pour le pb un certificat (une notion plutot qu'un objet...)
			//de plus on doit pouvoir borner la polynomialment la taille des certifcats possibles en fonction de la taille de l'instance
			abstract public Certificat cert();
			
			
		    //algo exponentiel de d�cision de la propri�t� bas�e sur l'�num�ration des certificats
			public boolean aUneSolution() {
				Certificat cert=this.cert();
				Iterator<Certificat> iterator=cert.ToutesLesInstances();
				while  (iterator.hasNext()){ //on balaye l'espace des certifcats 
		    		cert=iterator.next(); 
					if (cert.estCorrect(this)) { cert.display();  return true;} //un certificat au moins est correct!
				}
			    return false;
		    }
			
		    //algo non d�terministe : si il existe une solution AU MOINS UNE ex�cution retourne Vrai
			//si il n'en existe pas TOUTES les Ex�cutions retournent faux!
			public boolean aUneSolutionNonDeterministe() {
		     	Certificat cert=this.cert();
				cert.alea();
				if (cert.estCorrect(this)) { cert.display(); return true;}
		   		else return false;
		    }
		
}
